package com.algorithm.lesson_12;

import java.util.HashMap;
import java.util.Map;

/**
 * 找到字符串的最长无重复字符子串
 * 
 * @author Administrator
 *
 */
public class MaxNoRepeatSubStr {
	// str="abcd"， 返回 4
	// str="aabcb"， 最长无重复字符子串为"abc"， 返回 3。
	public static String getMaxNoRepeatSubStr(String str) {

		if (str == null || str.isEmpty()) {
			return "";
		}

		if (str.length() == 1) {
			return str;
		}

		Map<Character, Integer> map = new HashMap<>();

		char ch[] = str.toCharArray();

		map.put(ch[0], 0);// map记录字符c上一次出现的位置

		int pre = 0;
		int curLen = 1;// 当前最长子串长度
		int maxLen = 1;// 最长子串长度
		int index = 1;// 最长子串结束位置下标+1
		int i = 1;
		while (i < ch.length) {
			if (map.containsKey(ch[i])) {
				// 当前字符出现过
				int last = map.get(ch[i]);// 获取当前字符上一次出现的位置
				// pre表示以i-1位置字符结尾的最长子串最左端的下标
				if (last >= pre) {
					// 上一次出现的位置在pre~i-1之间
					pre = last + 1;
				}
				// 更新map中i的值
				map.put(ch[i], i);
			} else {
				// 当前字符未出现过
				map.put(ch[i], i);
			}
			curLen = i - pre + 1;
			if (curLen > maxLen) {
				maxLen = curLen;
				index = i + 1;
			}
			i++;
		}

		return str.substring(index - maxLen, index);
	}

	public int lengthOfLongestSubstring(String s) {
		if (s.length() == 0) {
			return 0;
		}
		int maxLen = 0;
		int len = 1;
		int checkIndex = 0;
		char[] chars = s.toCharArray();
		for (int i = 1; i < chars.length; i++) {
			len++;
			for (int j = checkIndex; j < i; j++) {
				if (chars[i] == chars[j]) {
					if (maxLen < len - 1) {
						maxLen = len - 1;
					}
					checkIndex = j + 1;
					len = i - j;
					break;
				}
			}
		}
		return Math.max(maxLen, len);
	}
}
